package com.xzx.algorithms.maxsubseqsum;

/**
 * 最大子列和问题
 * 给定N个整数的序列{ A1, A2, …, AN}，
 * 求最大子序列的和的最大值。
 * @author xinzhixuan
 * @version V1.0.0
 * @date 2020/8/30
 **/
public class MaxSubSeqSumDemo {
    public static void main(String[] args) {
        int[] list = {1, 3, 9,-3,-12,5,8,4,7,2};
        System.out.println(maxSubSeqSum01(list, list.length));
        System.out.println(maxSubSeqSum02(list, list.length));
        System.out.println(maxSubSeqSum04(list, list.length));

    }


    /**
     * 时间复杂度：T( N ) = O( N^3 )
     * 把最大子列和完全翻译了一遍，可以实现，但是算法比较low
     * 对于k循环是没必要的，，没必要每次都从i累加到j，可以把这个累计的结果保留，代码见算法二
     */
    public static int maxSubSeqSum01(int[] list, int length) {
        int maxSum = 0;
        for (int i=0; i<length; i++) {
            for (int j=i; j<length;j++) {
                int thisSum = 0;
                for(int k=i; k<=j; k++) {
                    thisSum += list[k];
                }
                if (thisSum > maxSum) {
                    maxSum = thisSum;
                }
            }
        }
        return maxSum;
    }

    /**
     * 时间复杂度：T( N ) = O( N^2 )
     * O(n^2)一般可以想办法优化成nlogn
     */
    public static int maxSubSeqSum02(int[] list, int length) {
        int maxSum = 0;
        for (int i=0; i<length; i++) {
            int thisSum = 0;
            for (int j=i; j<length;j++) {
                thisSum += list[j];
                if (thisSum > maxSum) {
                    maxSum = thisSum;
                }
            }
        }
        return maxSum;
    }

    /**
     * 在线处理，这个案例最快的算法O(n)
     * 这个算法的思路是实时的计算，来一个元素算一个元素
     */
    public static int maxSubSeqSum04(int[] list, int length) {
        int maxSum = 0;
        int thisSum = 0;
        for (int i=0; i<length; i++) {
            thisSum += list[i];
            if (thisSum > maxSum) {
                maxSum = thisSum;
            } else if (thisSum < 0) {// 说明这一个元素累加之后，整个和变小了，前半截的累计可以完全丢弃了，因为对和没有贡献了
                thisSum = 0;
            }
        }
        return maxSum;
    }
}
